//
// Description: 72. 编辑距离
// Created by Loading on 2022/2/24.
//

#include <bits/stdc++.h>

using namespace std;

int minDistance(string word1, string word2) {
    int m = word1.size();
    int n = word2.size();
    // dp 数组，dp[i][j] 表示word1的前i个字符转换为word2的前j个字符的最小编辑距离
    int dp[m + 1][n + 1];
    // 初始化 dp 数组
    for (int i = 0; i < m + 1; ++i) {
        dp[i][0] = i;
    }
    for (int i = 0; i < n + 1; ++i) {
        dp[0][i] = i;
    }

    /* 由dp[i - 1][j] -> dp[i][j]，只需在word1中删除末尾一个即可，则dp[i][j]最小可以为dp[i - 1][j] + 1 */
    /* 由dp[i][j - 1] -> dp[i][j]，只需在word1中末尾增加一个即可，则dp[i][j]最小可以为dp[i][j - 1] + 1 */
    /*
     * 由dp[i - 1][j - 1] -> dp[i][j]，只需修改word1的末尾字符即可，则dp[i][j]最小可以为dp[i - 1][j - 1] + 1
     * 特别地，注意：若末尾字符相等，则无需修改，dp[i][j]最小可以为dp[i - 1][j - 1]
     */
    for (int i = 1; i < m + 1; ++i) {
        for (int j = 1; j < n + 1; ++j) {
            if (word1[i - 1] == word2[j - 1]) {
                // 如果word1的第i个字符和word2的第j个字符本身就相同，则不需要修改
                dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1] - 1) + 1;
            } else {
                dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
            }
        }
    }

    return dp[m][n];
}

int main() {
    string word1 = "horse";
    string word2 = "ros";
    int res = minDistance(word1, word2);
    cout << res << endl;

    return 0;
}